package com.example.search;

public class InterpolationSearch {

    public static int interpolationSearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high && target >= arr[low] && target <= arr[high]) {
            // 避免除以零的情况
            if (arr[high] == arr[low]) {
                if (arr[low] == target) return low;
                return -1;
            }

            // 计算中间索引
            int mid = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

            // 如果目标值等于中间元素，返回中间索引
            if (arr[mid] == target) {
                return mid;
            }
            // 如果目标值小于中间元素，在左半部分查找
            else if (arr[mid] > target) {
                high = mid - 1;
            }
            // 如果目标值大于中间元素，在右半部分查找
            else {
                low = mid + 1;
            }
        }

        // 如果未找到目标值，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 13;

        int index = interpolationSearch(arr, target);

        if (index != -1) {
            System.out.println("目标值 " + target + " 所在的位置为: " + index);
        } else {
            System.out.println("目标值 " + target + " 不在数组中");
        }
    }
}